package gold.digger;

import gold.utils.InputUtil;

import java.util.*;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC332 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<String> findItinerary(List<List<String>> tickets) {
            Map<String, List<String>> orderMap = new HashMap<>();
            for (List<String> ticket : tickets) {
                String from = ticket.get(0);
                String to = ticket.get(1);
                if (orderMap.containsKey(from)) {
                    orderMap.get(from).add(to);
                    Collections.sort(orderMap.get(from));
                } else {
                    List<String> toList = new LinkedList<>();
                    toList.add(to);
                    orderMap.put(from, toList);
                }
            }

            List<String> curPath = new ArrayList<>(Arrays.asList("JFK"));
            findItineraryByDFS(orderMap, curPath, "JFK", tickets.size());
            return curPath;
        }

        public void findItineraryByDFS(Map<String, List<String>> orderMap, List<String> curPath, String curStart, int ticketsCount) {
            if (curPath.size() == ticketsCount + 1 || !orderMap.containsKey(curStart)) return;
            List<String> nextFlightDestinationSet = copyList(orderMap.get(curStart));
            for (String next : nextFlightDestinationSet) {
                orderMap.get(curStart).remove(next);
                curPath.add(next);
                findItineraryByDFS(orderMap, curPath, next, ticketsCount);
                if (curPath.size() == ticketsCount + 1) return;
                orderMap.get(curStart).add(next);
                Collections.sort(orderMap.get(curStart));
                curPath.remove(curPath.size() - 1);
            }
        }

        public List<String> copyList(List<String> original) {
            List<String> copySet = new LinkedList<>();
            for (String ele : original) {
                copySet.add(ele);
            }
            return copySet;
        }
    }

    public void run() {
        Solution solution = new Solution();
        String[][] arr = InputUtil.toDoubleStringArray("[[\"EZE\",\"AXA\"],[\"TIA\",\"ANU\"],[\"ANU\",\"JFK\"],[\"JFK\",\"ANU\"],[\"ANU\",\"EZE\"],[\"TIA\",\"ANU\"],[\"AXA\",\"TIA\"],[\"TIA\",\"JFK\"],[\"ANU\",\"TIA\"],[\"JFK\",\"TIA\"]]");
        List<List<String>> tickets = new ArrayList<>();
        for (String[] tick : arr) {
            tickets.add(Arrays.asList(tick));
        }
        System.out.println(solution.findItinerary(tickets));
    }

    public static void main(String[] args) throws Exception {
        LC332 an = new LC332();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
